POJ1182 【NOI2001】食物链 <种类并查集>

Problem

食物链

Description

动物王国中有三类动物，这三类动物的食物链构成了有趣的环形。吃，吃，吃。
有个动物，以编号。每个动物都是中的一种，但是我们并不知道它到底是哪一种。
人用两种说法对这个动物所构成的食物链关系进行描述：
一种说法是，表示和是同类。
二种说法是，表示吃。
人对个动物，用上述两种说法，一句接一句地说出句话，这句话有的是真的，有的是假的。当一句话满足下列三条之一时，这句话就是假话，否则就是真话。

当前的话与前面的某些真的话冲突，就是假话；
当前的话中或比大，就是假话；
当前的话表示吃，就是假话。

你的任务是根据给定的和句话，输出假话的总数。

Input

第一行是两个整数和，以一个空格分隔。
以下行每行是三个正整数，，，两数之间用一个空格隔开，其中表示说法的种类。
若，则表示和是同类。
若，则表示吃。

Output

只有一个整数，表示假话的数目。

Sample Input

Sample Output

标签：种类并查集

Solution

逻辑推理的题有一部分和并查集有关，此题是种类并查集的经典例题。
首先我们把每个动物分成三个点，对于点，点表示第个动物的种类，点表示第个动物的食物，点表示第个动物的天敌。
这样一来，提供信息：和同类，相当于提供三条信息：

、在同一个集中
、在同一个集中
、在同一个集中

于是我们
同理，提供信息：吃，相当于提供三条信息：

、在同一个集中
、在同一个集中
、在同一个集中

于是我们
如果在接到信息和同类后，发现和同类或和同类，则此信息与先前信息矛盾。因为对称性，我们不用再判断是否和或同类。同理可处理吃的情况。

Code

#include <iostream>
#include <cstdio>
#define MAX_N 50000
using namespace std;
int n, k, f[MAX_N*3+5], cnt = 0;
int get(int x) {
    if (x != f[x])	f[x] = get(f[x]);
    return f[x];
}
inline void merge(int x, int y) {
    int ancx = get(x), ancy = get(y);
    if (ancx != ancy)	f[ancx] = ancy;
    return;
}
int main() {
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n*3; i++)	f[i] = i;
    for (int i = 0; i < k; i++) {
        int s, x, y;
        scanf("%d%d%d", &s, &x, &y);
        if (x > n || y > n) {
            cnt++;
            continue;
        }
        if (s == 1) {
            if (get(x) == get(y+n) || get(x) == get(y+2*n)) {
                cnt++;
            } else {
                merge(x, y);
                merge(x+n, y+n);
                merge(x+2*n, y+2*n);
            }
        } else {
            if (x == y || get(x) == get(y) || get(x) == get(y+n)) {
                cnt++;
            } else {
                merge(x, y+2*n);
                merge(x+n, y);
                merge(x+2*n, y+n);
            }
        }
    }
    printf("%d", cnt);
    return 0;
}